Post-rebuttal update: The author's rebuttal addresses my (minor) concerns well, and my overall score remains the same. The approach is similar to earlier work such as: - M. Pilanci and M. J. Wainwright. The main innovations here are to extend this sketching technique to a wider class of convex objectives and to introduce a data-adaptive sketching technique that greatly improves the error bounds on the solution relative to a data-oblivious sketch. The proposed technique can also be performed iteratively to improve the accuracy of the solution without having to change the sketch matrix, so the sketch on the data only has to be performed once. Overall, I thought this was a high-quality paper.

We propose a new randomized optimization method for high-dimensional problems which can be seen as a generalization of coordinate descent to random subspaces. We show that an adaptive sampling strategy for the random subspace significantly outperforms the oblivious sampling method, which is the common choice in the recent literature. The adaptive subspace can be efficiently generated by a correlated random matrix ensemble whose statistics mimic the input data. We prove that the improvement in the relative error of the solution can be tightly characterized in terms of the spectrum of the data matrix, and provide probabilistic upper-bounds. We then illustrate the consequences of our theory with data matrices of different spectral decay.

We propose a new randomized optimization method for high-dimensional problems which can be seen as a generalization of coordinate descent to random subspaces. We show that an adaptive sampling strategy for the random subspace significantly outperforms the oblivious sampling method, which is the common choice in the recent literature. The adaptive subspace can be efficiently generated by a correlated random matrix ensemble whose statistics mimic the input data. We prove that the improvement in the relative error of the solution can be tightly characterized in terms of the spectrum of the data matrix, and provide probabilistic upper-bounds. We then illustrate the consequences of our theory with data matrices of different spectral decay.